In recent years, digital signatures (hereinafter referred to as signature) have been widely used for detection of data tampering and the like. One of the methods for generating signatures is RSA (Rivest Shamir Adleman) signature generation method. In this method, a signature S is generated by performing the operation S=MA^d mod n by using a signature key d with respect to a signature target message S.
The above-described signature key d is information that requires protection, and such information is referred to as confidential information hereinafter. Also, in this specification, the symbol ^ represents exponentiation operation, and the symbol * represents multiplication.
Here, during the processing of the above-described RSA signature generation, a value of the signature key d appears in a memory such as a RAM in a computer, or a register of a CPU. Therefore, the signature key d is at risk for being acquired in an unauthorized manner by analyzing such a memory.
As one of the techniques for preventing such illegal acquisition of the signature key d, Non-Patent Document 1 discloses a method for generating a signature without revealing the value of the signature key d to the memory.
In the method of Non-Patent Document 1, d1, d2, and d3 that satisfy a signature key generation equation d=(d1*d2)+d3 are respectively evaluated. Here, d1, d2 and d3 are split keys of the above described signature key, and generating the split keys from the signature key is referred to as the splitting of the signature key.
Based on the split keys (d1, d2, d3) and the signature key generation equation, operations are performed in order ofS1=M^d1 mod n S2=S1^d2 mod n S=S2*M^d3 mod n 
With these operations, the same signature S as the RSA signature generation equation S=M^d mod n can be obtained without using the signature key d. Also, during the signature generation processing, split keys (d1, d2, d3) appear in the memory instead of the signature key d. Therefore, the signature key d can be protected.    [Non-Patent Document 1] “Tamper-Resistance Evaluation of Signature Generation Software using Runtime-Data Search Method” Yokohama National University, Tsutomu Matsumoto, Hiroyuki Honda, SCIS 2005.